数据结构 ------ 图
一、图的定义
节点和边组成图，边可以有权值，也可以有方向，分为有向图和无向图。
1、无向图
无向图是指边没有规定方向的图，也可以认为是双向的。
边上的值代表边的权重，节点上的值代表节点的权重。
例如下面的无向图：
graph LR
A((V1)) ---|5| B((V2))
A((V1)) ---|2| D((V4))
B((V2)) ---|7| E((V5))
D((V4)) ---|4| C((V3))
C((V3)) ---|3| B((V2))
C((V3)) ---|5| E((V5))
2、有向图
有向图是指边有方向的图，是单向的。
例如下方的有向图：
graph LR
A((V1)) --->|5| B((V2))
A((V1)) --->|2| D((V4))
B((V2)) --->|7| E((V5))
D((V4)) --->|4| C((V3))
C((V3)) --->|3| B((V2))
C((V3)) --->|5| E((V5))
二、图的存储
1、邻接矩阵
先举例有向图，根据上面的有向图，可以得出下面的矩阵：
直接观察我们可以发现：
V1和V2之间存在值为5的边，那么在原矩阵中的第1行、第2列的值为5。
V1和V3之间没有直接的边，那么在矩阵中第1行、第3列的值为无穷。
第1行、第1列是无穷，说明节点到自己没有边也为无穷。
无向图同理，不过由于无向图的边是双向的，也就是说，在写V1到V2时，还得写V2到V1的边，因此可以得到以下矩阵：
可以发现，这个矩阵是关于主对角线对称的。
以上矩阵中的无穷，其实是可以替换为其他能够代表这两个节点没有边的数值，假如题目规定边的权值是小于1000的，就可以使用1005等数值来代表此处没有边，在第二个矩阵中，我使用了0表示此处没有边，其实在实际代码中，还是设置一个较大值比较方便判断。
2、邻接矩阵实现（C++）
首先，邻接矩阵的空间复杂度是：
假如有n个节点，那么就需要开 n * n 大小的矩阵，因此就是n平方。
其次，邻接矩阵的写法适合稠密图或者无向图，也就是边很多（稠密）的图（其中无向图因为是双向的所以边的数量会乘以2倍），否则会浪费大量空间。我们回头再看上面那个例子，5个节点的图需要开 5 * 5 = 25 大小的矩阵， 总共能记录25条边，然而上面的例子中只有6条有向边，实际上浪费了很多空间，下一个部分再介绍邻接表的写法，邻接表的写法是适合稀疏图的。
最后，上代码：
#include<iostream>
#include<vector>
using namespace std;
const int INF = 0x3f3f3f3f;//用16进制表示的int很大的值，常用于图的初始化
class Graph{
private:
vector<vector<int>> matrix;
int stage;//矩阵的阶数，其实就是顶点数量vertex
bool isUndirected;//默认是有向图
public:
Graph(int n, bool iU = false):
matrix(n, vector<int>(n, INF)), stage(n), isUndirected(iU) {}
void addEdge(int start, int end, int value = 1){
if(start < 1 || start > stage || end < 1 || end > stage
|| start == end){
cout << "输入数据非法！" << endl;
return;
}
matrix[start - 1][end - 1] = value;
if(isUndirected)
matrix[end - 1][start- 1] = value;//此处是无向图才需要添加
//不传入value的值默认为1，代表边无权值的图
}
void deleteEdge(int start, int end){
if(start < 1 || start > stage || end < 1 || end > stage
|| start == end){
cout << "输入数据非法！" << endl;
return;
}
matrix[start - 1][end - 1] = INF;
if(isUndirected)
matrix[end - 1][start- 1] = INF;//此处是无向图才需要添加
}
void printGraph(){
for(int i = 0; i < stage; i++){
for(int j = 0; j < stage; j++){
if(matrix[i][j] == INF) cout << "INF\t";
else cout << matrix[i][j] << "\t";
}
cout << endl;
}
}
int getSize(){
return stage;
}
bool hasEdge(int start, int end){
if(matrix[start - 1][end - 1] != INF) return true;
return false;
}
int getEdgeValue(int start, int end){
if(hasEdge(start, end)) return [start - 1][end - 1];
cout << "这两个节点之间没有边。" << endl;
return INF;
}
};
3、邻接表
先举例有向图，还是这个有向图：
graph LR
A((V1)) --->|5| B((V2))
A((V1)) --->|2| D((V4))
B((V2)) --->|7| E((V5))
D((V4)) --->|4| C((V3))
C((V3)) --->|3| B((V2))
C((V3)) --->|5| E((V5))
我们来写出它的邻接表：
graph LR
A[V1] --->|5| A1[V2] --->|2| A2[V4]
B[V2] --->|7| B1[V5]
C[V3] --->|3| C1[V2] --->|5| C2[V5]
D[V4] --->|4| D1[V3]
E[V5]
在这里，从上往下V1~V5，我们将这部分看作一个数组，这个数组的下标表示起始节点，数组存储的值的数据类型是我们定义的边结构体，其中包括边的权重和边的目标节点。
4、邻接表实现（C++）
可以使用二维数组实现，也可以使用链表，这里写一个二维数组的实现方式。
#include<iostream>
#include<vector>
using namespace std;
struct Edge{
int value;
int to;
};
class Graph{
private:
vector<vector<Edge>> adjList;
int vertex;
public:
Graph(int n):
adjList(n), vertex(n){}
void addEdge(int start, int end, int value){
if(start < 1 || start > vertex || end < 1 || end > vertex
|| start == end){
cout << "输入数据非法。" << endl;
return;
}
adjList[start - 1].push_back({value, end});
}
void deleteEdge(int start, int end){
if(start < 1 || start > vertex || end < 1 || end > vertex
|| start == end){
cout << "输入数据非法。" << endl;
return;
}
auto it = adjList[start - 1].find(end);
if(it != adjList[start - 1].end())
adjList[start - 1].erase(it);
}
};
三、图的遍历方式
不重不漏地遍历所有节点
例子：
graph LR
A((V1)) --->|5| B((V2))
A((V1)) --->|2| D((V4))
B((V2)) --->|7| E((V5))
D((V4)) --->|4| C((V3))
C((V3)) --->|3| B((V2))
C((V3)) --->|5| E((V5))
1、深度优先搜索（DFS）
先给出深度优先的遍历结果，假如我们从V1开始遍历：V1 → V2 → V5 → V4 → V3（其实是不唯一的）
根据这次遍历结果不难发现，V1 → V2 → V5，深度在逐渐增加，然而V5没有下一个节点，便回头到V2，V2也没有除了V5以外的其他节点，便回到V1，V1有除了V2以外的节点V4，便遍历V4，然后是V3，到达V3后，所有节点被遍历完了，结束遍历。
假设V1先遍历V4呢？遍历结果可以是：V1 → V4 → V3 → V2 → V5 或者 V1 → V4 → V3 → V5 → V2
道理也是一样的，先往深处找，如果没有就回头查看其他路径，直到所有节点都被遍历。
假如图采用的邻接矩阵的方法，可以得到DFS的C++代码，这里使用的递归方式，实际上也可以直接使用STL的栈（stack）：
class Graph{
private:
vector<vector<int>> matrix;
int stage;
bool isUndirected;
void DFSUtil(int node, vector<bool>& visited) {
visited[node] = true;
cout << node;
for (int i = 0; i < stage; ++i) {
if (matrix[node - 1][i] != INF && !visited[i + 1]) {
cout << " --> ";
DFSUtil(i + 1, visited);
}
}
}
public:
//省略其他代码...
void DFS(int start = 1) {
if (start < 1 || start > stage) {
cout << "起始节点不存在。" << endl;
return;
}
vector<bool> visited(stage + 1, false);
// 先从 start 开始遍历
cout << "从起始节点 " << start << " 开始遍历：" << endl;
DFSUtil(start, visited);
cout << endl;
// 遍历其他连通块
for (int i = 1; i <= stage; ++i) {
if (!visited[i]) {
cout << "从其他连通块的节点 " << i << " 开始遍历：" << endl;
DFSUtil(i, visited);
cout << endl;
}
}
cout << "所有节点遍历完成。" << endl;
}
};
首先我们在public的部分定义了DFS，并且允许传入自由选择的起始遍历节点，接下来分析DFS的函数体：
-
判断用户输入的start节点是否存在，如果小于1或者大于最大节点编号stage，提示错误。
-
visited数组用于记录遍历了哪些节点，初始化所有节点都没有被遍历，即false。
-
然后传入递归函数DFSUtil。
-
如果这不是一个连通图，visited中就会还有未遍历的节点，我们再遍历一遍visited数组，找到未遍历的节点，继续递归，这样就能保证所有节点都被成功遍历。
然后分析DFSUtil函数，参数是节点node和visited数组，函数体：
-
将传入的节点的visited变为true，表示该节点已经被遍历。
-
输出该节点，因为这个节点被成功遍历了。
-
查找这个节点的边，如果有边，即matrix[node - 1][i] != INF（边值不等于无穷大），那么就递归边指向的节点，即递归 i + 1，因为是这里是下标，所以要 + 1 变成节点的值，继续传入visited数组。
邻接表的实现方式也差不多道理。
2、广度优先搜索（BFS）
还是先看结论，假如从V1开始遍历：V1 → V2 → V4 → V5 → V3（结果也不唯一）
V1之后直接遍历了所有V1相邻的节点（V2和V4），而不是：先走其中一个，等到走完其中一条路再走另一条。
很容易理解，但是有一个细节，V2和V4的位置是可以交换的，如果交换了位置，后面对应的V5和V3也会跟着交换：V1 → V4 → V2 → V3 → V5，因为这里我们先遍历了V4，就应该先遍历V4的边，V4的边连着V3，所以先写V3，再写V2连着的V5。
上面DFS用的邻接矩阵，这里写采用邻接表的BFS实现方式，我这里直接使用STL的队列（queue）：
struct Edge{
int value;
int to;
};
class Graph{
private:
vector<vector<Edge>> adjList;
int vertex;
void _BFS(int startNode, vector<bool>& visited) {
queue<int> q;
visited[startNode] = true;
q.push(startNode);
bool first = true;
while(!q.empty()){
int node = q.front();
q.pop();
if(first){
cout << node;
first = false;
}
else{
cout << " → " << node;
}
for(auto& edge: adjList[node - 1]){
int neighbor = edge.to;
if(!visited[neighbor]){
q.push(neighbor);
visited[neighbor] = true;
}
}
}
}
public:
//省略其他代码...
void BFS(int start = 1) {
if (start < 1 || start > vertex) {
cout << "起始节点不存在。" << endl;
return;
}
vector<bool> visited(vertex + 1, false);
// 先从 start 节点开始遍历
cout << "从起始节点 " << start << " 开始 BFS：" << endl;
_BFS(start, visited);
cout << endl;
// 遍历未访问的其他连通块
for (int i = 1; i <= vertex; ++i) {
if (!visited[i]) {
cout << "从其他连通块的节点 " << i << " 开始 BFS：" << endl;
_BFS(i, visited);
cout << endl;
}
}
cout << "所有节点 BFS 完成。" << endl;
}
};
先解释BFS，也是传入指定的开头节点，不传入就默认为1，函数体：
-
判断传入的节点是否合理。
-
visited数组记录被遍历的节点。
-
遍历start节点。
-
遍历其他连通块。
然后是 _BFS，传入开头节点和visited数组，函数体：
-
头节点标为true，加入队列。
-
first用来标志是否是第一个节点，后面循环中，如果是第一个节点就不输出" → "，剩下的节点都会输出：" → " + 当前节点值。
-
进入循环，获取队首元素，判断后输出，弹出队首元素，查找队首元素的其他边指向的节点，找到没有遍历的节点加入队伍。
这样根据队列一层一层加入就会一层一层输出了。
说实话，我这里的adjList处理得没有那么好，建议在初始化时直接开成n + 1，然后从1开始添加节点，这样就不用那么麻烦地去处理角标和点的关系了，每次 +1 ， - 1容易让人出错。
四、最小生成树
1、定义
在一个图中，通过最短的边访问所有节点，这样的边和节点组成的树就是最小生成树。
graph LR
B((V2)) ---|5| D((V4))
B((V2)) ---|1| A((V1))
A((V1)) ---|5| C((V3))
B((V2)) ---|6| C((V3))
A((V1)) ---|4| D((V4))
A((V1)) ---|6| E((V5))
C((V3)) ---|3| E((V5))
D((V4)) ---|2| F((V6))
A((V1)) ---|4| F((V6))
E((V5)) ---|6| F((V6))
例如这个无向图，我们将通过下面两种算法来找其最小生成树。
2、Prim算法
也称加点法，初始最小生成树中为空，给定初始点，向树中添加初始点，然后查找初始点的相邻点，找到距离最近的节点添加到树中，然后查找初始点和新添加的点的整体的相邻点，找到距离最近的添加到树中，重复操作直至访问到所有点。
上述无向图，假如初始点为V2，V2添加至树中：
-
V2相邻点中距离最近的点为V1，距离为1，加入树中。
-
V2和V1整体，距离最近的点有V4和V6，距离为4，选择其中一个添加到树中，这里添加V4。
-
V2、V1、V4整体，距离最近的为V6，距离为2，加入树中。
-
V2、V1、V4、V6整体，距离最近的为V3，距离为5，加入树中。
-
V2、V1、V4、V6、V3整体，距离最近的为V5，距离为3，加入树中。
则可得：
graph LR
B((V2)) ---|1| A((V1))
A((V1)) ---|5| C((V3))
A((V1)) ---|4| D((V4))
C((V3)) ---|3| E((V5))
D((V4)) ---|2| F((V6))
这就是通过Prim算法得到的最小生成树。
如果在上面的第2步中选择添加V6，则会得到另一个最小生成树：
graph LR
B((V2)) ---|1| A((V1))
A((V1)) ---|5| C((V3))
A((V1)) ---|4| F((V6))
C((V3)) ---|3| E((V5))
F((V6)) ---|2| D((V4))
因此最小生成树可能不唯一。
邻接矩阵
用邻接矩阵存储的图，使用Prim算法获取最小生成树的C++代码：
class Graph{
private:
vector<vector<int>> matrix;
int stage;//矩阵的阶数，其实就是顶点数量vertex
bool isUndirected;
public:
//省略其他代码...
vector<vector<int>> PrimMST() {
vector<vector<int>> MST(stage, vector<int>(stage, INF));
vector<bool> isVisited(stage, false);
isVisited[0] = true;
for (int k = 1; k < stage; ++k) {
int s = -1, e = -1, len = INF;
for (int i = 0; i < stage; ++i) {
if (isVisited[i]) {
for (int j = 0; j < stage; ++j) {
if (!isVisited[j] && matrix[i][j] < len) {
len = matrix[i][j];
s = i;
e = j;
}
}
}
}
if (s == -1 || e == -1) return vector(0, vector<int>(0));
//图不连通
MST[s][e] = len;
if (isUndirected)
MST[e][s] = len;
isVisited[e] = true;
}
cout << "最小生成树为：" << endl;
for (int i = 0; i < stage; ++i) {
for (int j = 0; j < stage; ++j) {
if (MST[i][j] == INF) cout << "∞";
else cout << MST[i][j];
if (j < stage - 1) cout << ' ';
}
cout << endl;
}
return MST;
}
};
对于PrimMST函数，做以下解释：
-
首先定义最小生成树的邻接矩阵MST，以及记录访问节点的数组isVisited，同时此数组可以标志MST已经有哪些节点，方便查找树整体的相邻节点，初始节点设置为已访问。
-
因为已经加入了第一个节点，所以我们只需访问剩下的节点，即stage - 1次，所以外层循环k从1~stage，左闭右开。
-
定义s、e和len，分别代表边从s指向e，长度为len，初始长度无限大。
-
i，j循环，遍历原图，其中已访问的节点，就可以找到已访问节点的相邻节点，选择长度最短的未访问节点记录在s、e和len中。
-
如果s、e没被成功赋值，则说明图不连通，没有适合的边，直接退出函数，返回一个空的二维数组。如果赋值成功，更新MST中的值，如果是无向图，两个边都更新，标记e节点，就是新添加的节点为已访问。
-
外层循环结束，打印MST结果，然后返回MST的二维数组。
时间复杂度， 取决于定点数V：
邻接表
采用邻接表的图，使用Prim算法，获取最小生成树的时间复杂度会比较低：
struct Edge{
int weight;
int to;
Edge(int w, int t):weight(w), to(t){}
};
Class Graph{
private:
vector<vector<Edge>> adjList;
int vertex;
bool isUndirected;
public:
Graph(int v, bool iU = false):vertex(v), isUndirected(iU){
adjList.resize(vertex);
}
void PrimMST(int start = 0){
vector<bool> isVisited(vertex, false);
vector<int> minWeight(vertex, INF);
vector<int> MST(vertex, -1);
using PII pair<int, int>;
priority_queue<PII, vector<PII>, greater<>> pq;
minWeight[start] = 0;
pq.emplace(0, start);
while(!pq.empty()){
int u = pq.top().second;
pq.pop();
if(isVisited[u]) continue;
isVisited[u] = true;
for(const Edge& edge : adjList[u]){
int v = edge.to, w = edge.weight;
if(!isVisited[v] && w < minWeight[v]){
minWeight[v] = w;
parent[v] = u;
pq.emplace(w, v);
}
}
}
cout << "最小生成树的结构为：" << endl;
int totalWeight = 0;
for(size_t i = 0; i < vertex; i++){
if(parent[i] != -1){
cout << MST[i] << " ---|"
<< minWeight[i] << '| '
<< i << endl;
totalWeight += minWeight[i];
}
}
cout << "最小生成树的总权重：" << totalWeight << endl;
}
};
对PrimMST函数的解释：
-
开始节点是可以选择的，默认为0开始，isVisited：某个节点是否被访问，初始化全部为否。
-
minWeight：到达节点v的最短边的长度w，初始化所有边长度为无穷INF；MST：到达节点v的出发节点u，初始化所有节点的出发节点为-1；两个数组的索引：目的节点v；
-
pq：优先队列，先进先出，底层容器（vector），存储元素的数据结构：pair<int, int>，排序逻辑：从字典序小到大（greater<>），实际上就是存储Edge(weight, to)，不过是排序存储，weight最小的会排到队伍的首部。
-
从start开始，到达节点start的边长度为0，即minWeight[start] = 0，放入队列中，pq.emplace(0, start)。
-
循环（结束条件队列pq为空），第一次进入：u = 队首元素的第二项，即u = (0, start)中的start，弹出队首元素（已经被使用了，所以弹出），如果u节点没有被访问，标记为已访问，开始内层循环：查找u的所有边edge，如果edge指向的节点没有被访问，并且edge的长度比记录的边要短，更新MST和minWeight，将该w，v组合添加到队列。由于该队列是优先队列，队首元素始终是u的所有边中最短的那个，即使最短边是后加入的。
-
之后的每次循环：u = 队首元素，之前循环中最短的边的第二项，弹出该最短边，其他地方同理。重点是，对于任意一个节点v，即使在之前我们向队列中和数组中添加了较长的边，被访问标记是没有变为true的，所以在之后的循环如果找到的更短边，也会加入队列，并且，更短边在队列中的位置会比之前的边靠前。最终会先访问到更短边并且更新访问标记为true，之后的长边就会因为节点已访问而被无视直接弹出。
时间复杂度：
3、Kruskal算法
也称加边法，初始最小生成树也为空，所有点为孤立点，每次向树中添加一个原图中最小的边，但是此最小的边的两个端点不能在同一个连通分量内，若不在，则添加此边，若不在，则跳过此边，结束条件依旧是所有的点均被访问。
graph LR
B((V2)) ---|5| D((V4))
B((V2)) ---|1| A((V1))
A((V1)) ---|5| C((V3))
B((V2)) ---|6| C((V3))
A((V1)) ---|4| D((V4))
A((V1)) ---|6| E((V5))
C((V3)) ---|3| E((V5))
D((V4)) ---|2| F((V6))
A((V1)) ---|4| F((V6))
E((V5)) ---|6| F((V6))
针对上述无向图，现在所有点为孤立点（任意两点之间没有边），有：
-
原图中V2与V1之间的边最短，为1，并且V2与V1未连通，添加此边。
-
V4与V6之间边最短，为2，并且这两点未连通，添加此边。
-
V3与V5之间边最短，为3，并且这两点未连通，添加此边。
-
V1与V4，或者V1与V6之间边最短，为4，并且这两点未连通，任选一个添加（这里便出现两种情况），此处添加V1与V4。
-
V1与V6之间边最短，为4，但是这两点连通，V1→ V4 → V6，因此不添加，跳过。
-
V1与V3之间边最短，为5，这两点未连通，添加此边。
-
至此所有点均连通，结束算法。
由第4步可以看出，和Prim算法一样，出现了多种情况，所以，也可以得到两个最小生成树。
邻接表
Kruskal算法更适合稀疏图，邻接矩阵往往用来存储稠密图，如果在邻接矩阵中使用该算法，往往时间复杂度很大，所以这里只介绍邻接表的算法。
采用邻接表存储的图，使用Kruskal算法的C++代码：
struct Edge{
int weight;
int from;
int to;
Edge(int f, int t, int w) : from(f), to(t), weight(w) {}
bool operator<(const Edge &b)const{
return weight < b.weight;
}
};
Class Graph{
private:
vector<vector<Edge>> adjList;
int vertex;
bool isUndirected;
int KruskalFind(vector<int> &parent, int vertex){
if(parent[vertex] == vertex)
return vertex;
else
return parent[vertex] = KruskalFind(parent, parent[vertex]);
}
void KruskalUnit(vector<int> &parent, int vertex_a, int vertex_b){
int fa = KruskalFind(parent, vertex_a);
int fb = KruskalFind(parent, vertex_b));
if(fa != fb)
parent[fa] = fb;
}
public:
Graph(int v, bool iU = false):vertex(v), isUndirected(iU){
adjList.resize(vertex);
}
void KruskalMST(){
vector<vector<Edge>> MST(vertex);
int parent[vertex];
for(int i = 0; i < vertex; i++){
parent[i] = i;
}
vector<Edge> asc_adjList;
for(size_t i = 0; i < vertex; i++){
for(auto edge : adjList[i]){
if(isUndirected){
if(edge.from < edge.to)
asc_adjList.push_back(edge);
}
else
asc_adjList.push_back(edge);
}
}
sort(asc_adjList.begin(), asc_adjList.end());
for(auto edge : asc_adjList){
if(KruskalFind(parent, edge.from) == KruskalFind(parent, edge.to))
continue;
MST[edge.from].push_back(edge);
KruskalFind(parent, edge.from, edge.to);
}
cout << "最小生成树为：" << endl;
for(size_t i = 0; i < vertex; i++){
for(auto edge : MST[i]){
cout << edge.from << "---" << edge.to << endl;
}
}
}
};
现在可以来解释一下该部分代码：
-
为结构体添加一个from，用来存储边的起始节点。另外重载小于运算符，让sort函数能够对asc_adjList中的边进行大小排序。
-
parent数组、KruskalFind函数和KruskalUnit函数，这三个部分是并查集的知识，可以用于快速判断两个节点是否位于同一个树中，也可以快速连接两个节点到同一个树。代码中我们通过这种方式判断两个节点是否在同一个连通块，如果不是，则添加这个最小边，如果是，则跳过这个最小边。
五、Dijkstra最短路径算法
Dijkstra算法用于计算某一点到其他所有点的最短路径的距离，Dijkstra 算法不能处理负权边。
graph LR
A((a)) ---> |2| B((b))
B((b)) ---> |1| C((c))
A((a)) ---> |5| C((c))
B((b)) ---> |3| D((d))
C((c)) ---> |3| D((d))
D((d)) ---> |1| E((e))
C((c)) ---> |4| E((e))
D((d)) ---> |4| F((f))
C((c)) ---> |1| F((f))
E((e)) ---> |1| F((f))
给定一个起始点，此处起始点假设为a，定义数组visited表示某节点被访问，初始化a节点被访问，其它所有节点未被访问，定义数组dist表示a节点到其他节点的距离，初始化a到自己为0，到其他为无穷，有：
-
遍历a的相邻节点，更新相邻节点的dist数组，a --->|2| b，a --->|5| c，可以发现b的距离为2，比原dist中无穷小，更新值为2，c的距离为3，比原dist中的无穷小，更新值为5，此时dist：{ 0, 2, 5, INF, INF, INF }。
-
选择相邻节点中最近的那一个，此处为b，标记b为已访问，因为此边为从a到b的直达且最短边，所以不可能有a从其他路径到b还更近，所以b被标记为已访问。
-
将已访问的所有点视为整体，查找已访问的节点的相邻节点，b --->|1| c，b --->|3| d， a --->|5| c，可以发现a ---> b ---> c更近，值为2 + 1 = 3，比原dist中的5要小，更新，同理，更新d节点的值，此时dist：{ 0, 2, 3, 5, INF, INF}。
-
同理，因为ab整体中有最短边且直达c，所以标记c为已访问。
-
重复更新操作和标记操作直至结束，这样就完成了该算法的计算。
通过邻接表存储的图的Dijkstra算法的C++实现：
struct Edge{
int weight;
int to;
Edge(int w, int t):weight(w), to(t){}
};
class Graph{
private:
vector<vector<Edge>> adjList;
int vertex;
bool isUndirected;
public:
Graph(int v, bool iU = false):vertex(v), isUndirected(iU){
adjList.resize(vertex);
}
vector<int> Dijkstra(int start){
vector<bool> visited(vertex, false);
vector<int> dist(vertex, INF);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
pq.emplace(0, start);
dist[start] = 0;
while(!pq.empty()){
int u = pq.top().second;
pq.pop();
if (visited[u]) continue;
visited[u] = true;
for(auto edge : adjList[u]){
int v = edge.to;
int w = edge.weight;
if(!visited[v] && dist[v] > dist[u] + w){
dist[v] = dist[u] + w;
pq.emplace(dist[v], v);
}
}
}
return dist;
}
};
大功告成。
六、Floyd最短路径算法
Floyd算法用于求任意两点之间的路径大小，相较于Dijkstra，Floyd可以处理负数权值的边。
graph TD
A((0)) ---> |6| B((1))
B((1)) ---> |10| A((0))
A((0)) ---> |13| C((2))
C((2)) ---> |5| A((0))
B((1)) ---> |4| C((2))
如图三个节点，要求任意两点之间的最短路径长度，维护一个二维数组.
由图可以得到第一个表D(-1)，表示在未引入任何中间点之前的初始距离表，直接使用边权作为初始路径。
例如：第1行，第0列，表示节点1到节点0的路径长度为10：
| D(-1) | 0 | 1 | 2 | |:-----:|:---:|:---:|:---:| | 0 | 0 | 6 | 13 | | 1 | 10 | 0 | 4 | | 2 | 5 | INF | 0 |
接下来，我们将所有点作为中间点来更新表格，依照的对象是上一个表格。
对角线是不用更新的，因为自己到自己永远是0。
当0为中间点时，第0行第0列是不用更新的，因为此时的0同时也是目标点或者起始点，既然是目标点和起始点，那也就没有中间点，所以无需更新。
所以我们需要更新的位置只有1 → 0 → 2和2 → 0 → 1，下划线部分是可能需要更新的位置，额外高亮的部分是实际更新的点。
1 → 0 → 2，显而易见的是，从1到0再到2的路径长度为：10 + 13 = 26，大于原路径长度4，所以无需更新。
2 → 0 → 1，从2到0再到1的路径长度为：5 + 6 = 11，小于原路径长度无穷，所以更新。
| D(0) | 0 | 1 | 2 | |:----:|:---:|:------------------------:|:----------:| | 0 | 0 | 6 | 13 | | 1 | 10 | 0 | 4 | | 2 | 5 | 11 | 0 |
以1为中间点时依照上一个表格，需要更新的位置只有0 → 1 → 2和2 → 1 → 0。
0 → 1 → 2，路径长度为：6 + 4 = 10，小于原路径长度13，更新。
2 → 1 → 0，路径长度为：11 + 10 = 21，大于原路径长度5，不更新。
| D(1) | 0 | 1 | 2 | |:----:|:----------:|:---:|:------------------------:| | 0 | 0 | 6 | 10 | | 1 | 10 | 0 | 4 | | 2 | 5 | 11 | 0 |
以2为中间点时依照上一个表格，需要更新的位置只有0 → 2 → 1和1 → 2 → 0。
0 → 2 → 1，路径长度为：10 + 11 = 21，大于原路径长度6，不更新。
1 → 2 → 0，路径长度为：4 + 5 = 9，小于原路径长度10，更新。
| D(2) | 0 | 1 | 2 | |:----:|:-----------------------:|:----------:|:---:| | 0 | 0 | 6 | 10 | | 1 | 9 | 0 | 4 | | 2 | 5 | 11 | 0 |
所以我们就得到了最终的表格D(2)，这里面记录了任意两点的最短路径。
graph TD
A((0)) ---> |6| B((1))
B((1)) ---> |10| A((0))
A((0)) ---> |13| C((2))
C((2)) ---> |5| A((0))
B((1)) ---> |4| C((2))
除此之外，Floyd还可以记录最短路径的过程，也就是从哪里开始，经过哪些点，到达哪个目的点。
使用一个路径表，路径表记录的是从起点到终点的最短路径中，终点之前的那个节点是谁，用来递归构造完整路径，根据原图进行初始化，可得：
| P(-1) | 0 | 1 | 2 | |:-----:|:---:|:---:|:---:| | 0 | -1 | 0 | 0 | | 1 | 1 | -1 | 1 | | 2 | 2 | -1 | -1 |
例如，第1行第0列表示，从节点1到节点0，最后一个节点是0，上一个节点是1。
同样是以每一个点为中间点，根据上一个表格更新得到下一个表格。
同理，对应行列不用更新，我以下划线标注此表可能需要更新的部分，额外高亮部分是实际更新的部分。
以0为中间点。
1 → 0 → 2，显而易见的是，从1到0再到2的路径长度为：10 + 13 = 26，大于原路径长度4，所以无需更新，那么，路径的过程也不用更新。
2 → 0 → 1，从2到0再到1的路径长度为：5 + 6 = 11，小于原路径长度无穷，所以更新，因此路径过程中，原路径2 → 1变为2 → 0 → 1，则最后一个节点1的上一个节点为0，表格值更新为0。
| P(0) | 0 | 1 | 2 | |:----:|:---:|:-----------------------:|:----------:| | 0 | -1 | 0 | 0 | | 1 | 1 | -1 | 1 | | 2 | 2 | 0 | -1 |
以1为中间点。
0 → 1 → 2，路径长度为：6 + 4 = 10，小于原路径长度13，更新，路径改变，更新为1。
2 → 1 → 0，路径长度为：11 + 10 = 21，大于原路径长度5，不更新。
| P(1) | 0 | 1 | 2 | |:----:|:----------:|:---:|:-----------------------:| | 0 | -1 | 0 | 1 | | 1 | 1 | -1 | 1 | | 2 | 2 | 0 | -1 |
以2为中间点。
0 → 2 → 1，路径长度为：10 + 11 = 21，大于原路径长度6，不更新。
1 → 2 → 0，路径长度为：4 + 5 = 9，小于原路径长度10，更新。
| P(2) | 0 | 1 | 2 | |:----:|:-----------------------:|:----------:|:---:| | 0 | -1 | 0 | 1 | | 1 | 2 | -1 | 1 | | 2 | 2 | 0 | -1 |
至此，可以查找任意两点的最短路径的过程。
比如，从1到0的最短路径，先找到第1行第0列，最后一个节点是0，前一个节点为2，那么就是0 ← 2， 然后再查找1到2的最短路径，找到第1行第2列，发现结果是1，则说明2的前一个节点是1，那么就有0 ← 2 ← 1，倒过来就是路径的过程了，所以最终路径为：1 → 2 → 0。
由于Floyd算法本来就使用了二维数组来存储，那么邻接矩阵再适合不过了：
class Graph{
private:
vector<vector<int>> matrix;
int stage;//矩阵的阶数，其实就是顶点数量vertex
bool isUndirected;
public:
//省略其他部分代码...
void Floyd(){
vector<vector<int>> dist(matrix);
vector<vector<int>> path(n, vector<int>(n, -1));
for(int i = 0; i < stage; i++){
for(int j = 0; j < stage; j++){
if(dist[i][i] != INF && i != j){
path[i][j] = i;
}
}
}
for (int k = 0; k < stage; k++) {
for (int i = 0; i < stage; i++) {
for (int j = 0; j < stage; j++) {
if (dist[i][k] < INF && dist[k][j] < INF &&
dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
path[i][j] = path[k][j];
}
}
}
}
cout << "最短距离矩阵：" << endl;
for (int i = 0; i < stage; i++) {
for (int j = 0; j < stage; j++) {
if (dist[i][j] == INF) cout << "INF ";
else cout << dist[i][j] << " ";
}
cout << endl;
}
cout << "\n任意两点路径示例 (格式: from -> to: path):" << endl;
for (int i = 0; i < stage; i++) {
for (int j = 0; j < stage; j++) {
if (i != j && dist[i][j] != INF) {
cout << i << " -> " << j << ": ";
printPath(path, i, j);
cout << j << endl;
}
}
}
}
void printPath(vector<vector<int>>& path, int u, int v) {
if (path[u][v] == -1) return;
printPath(path, u, path[u][v]);
cout << path[u][v] << " -> ";
}
};
七、拓扑排序
根据节点的入度决定节点的输出顺序，只输出入度为零的节点。
拓扑排序只能用于没有环的图，如果图中出现了环，环中的节点都肯定有入度：
graph LR
A((a)) ---> B((b))
B((b)) ---> C((c))
C((c)) ---> D((d))
D((d)) ---> E((e))
E((e)) ---> A((a))
没有入度为零的节点，则不能进行拓扑排序。
接下来进行一个拓扑排序的例子分析。
例如该图：
graph LR
A((a)) ---> E((e))
E((e)) ---> D((d))
A((a)) ---> C((c))
C((c)) ---> D((d))
A((a)) ---> B((b))
B((b)) ---> C((c))
-
a节点入度为零，输出a，删除a节点。
-
b，e节点入度为零，则任选其一，此时代表拓扑排序不唯一，此处输出b，删除b节点。
-
c，e节点入度为零，任选其一，此处输出c，删除c节点。
-
e节点入度为零，输出e，删除e节点。
-
d节点入度为零，输出d，删除d节点，结束。
-
最终结果：a → b → c → e → d（不唯一，第2步和第3步可以选择不同的输出）。
邻接表的C++拓扑排序实现：
struct Edge{
int weight;
int to;
Edge(int w, int t):weight(w), to(t){}
};
Class Graph{
private:
vector<vector<Edge>> adjList;
int vertex;
bool isUndirected;
public:
//省略其他代码...
void topSort() {
vector<int> indegree(vertex, 0);
// 计算所有顶点的入度
for (int i = 0; i < vertex; i++) {
for (auto& edge : adjList[i]) {
indegree[edge.to]++;
}
}
queue<int> q;
// 将所有入度为0的顶点加入队列
for (int i = 0; i < vertex; i++) {
if (indegree[i] == 0) {
q.push(i);
}
}
bool first = true;
while (!q.empty()) {
int u = q.front(); q.pop();
if (!first) cout << " ---> ";
first = false;
cout << u;
// 遍历其邻接点，并更新入度
for (auto& edge : adjList[u]) {
indegree[edge.to]--;
if (indegree[edge.to] == 0) {
q.push(edge.to);
}
}
}
// 检查是否有环（即还有点入度不为0）
for (int i = 0; i < vertex; i++) {
if (indegree[i] != 0) {
cout << "\n图中存在环，无法拓扑排序" << endl;
return;
}
}
}
};